/**
 * https://leetcode-cn.com/problems/longest-common-prefix/
 * 最长公共前缀
 * @param strs 
 */
const longestCommonPrefix = (strs: string[]): string => {

    /**
     * 查找s -> e 的最长公共前缀
     * @param s 
     * @param e 
     */
    const find = (s: number, e: number): string => {
        // 边界判断
        if (s === e) return strs[s]

        // 获取中间
        const m = (s + e) >> 1

        // 左边
        let left = find(s, m);

        // 右边 
        let right = find(m + 1, e)

        // 求left和right的最长公共前缀
        let str = '',
            l = 0,
            r = 0,
            lLen = left.length,
            rLen = right.length;

        // 直到某一边到了结尾
        while (l < lLen && r < rLen) {
            // 前缀不一样
            if (left[l] !== right[r]) {
                break;
            }

            // 前缀一样, 拼接到str 
            str += left[l]
            l++; 
            r++
        }
        return str;
    }

    return find(0, strs.length - 1);
};

console.log(longestCommonPrefix(["flower","flow","flight"]))
console.log(longestCommonPrefix(["dog","racecar","car"]))